package com.study.sort;

import static org.springframework.test.web.client.match.MockRestRequestMatchers.anything;

import java.util.ArrayList;
import java.util.Arrays;
import java.util.Iterator;
import java.util.List;

public class Sort {

	private Integer[] array;

	public Sort(Integer[] array) {
		super();
		this.array = array;
	}

	// 冒泡排序
	public void bubbleSort() {

		if (this.array != null) {
			for (int i = 0; i < this.array.length; i++) {
				for (int j = i; j < this.array.length; j++) {
					if (this.array[i] > this.array[j]) {
						int tmp = this.array[i];
						this.array[i] = this.array[j];
						this.array[j] = tmp;
					}
				}
			}
		}

	}

	public void insertionSort() {
		int i, j, tmp;
		if (this.array != null) {
			for (i = 1; i < this.array.length; i++) {
				tmp = this.array[i];
				//// 如果第i个元素小于第j个，则第j个向后移动
				for (j = i - 1; j >= 0 & tmp < this.array[j]; j--) {
					this.array[j + 1] = this.array[j];
				}
				this.array[j + 1] = tmp;
			}
		}
	}

	public void quickSort(int begin, int end) {
		if (begin == end)
			return;
		int idx = dividearray(this.array, begin, end);
		if (begin < end) {
			quickSort(begin, idx - 1);
			quickSort(idx + 1, end);
		}

	}

	private int dividearray(Integer[] array, int begin, int end) {
		int base = this.array[begin];
		int result = begin + 1, tmp = 0; // 假设result 为比base 值大的元素的下标
		for (int i = begin + 1; i <= end; i++) {
			if (this.array[i] < this.array[begin]) {
				tmp = this.array[result];
				this.array[result] = this.array[i];
				this.array[i] = tmp;
				result++;
			}
		}
		tmp = this.array[begin];
		this.array[begin] = this.array[result - 1];
		this.array[result - 1] = tmp;
		return result - 1;
	}

	public void selectionSort() {
		int len = this.array.length;
		int idx, tmp = 0;
		for (int j = 0; j < len; j++) {
			idx = j;
			for (int i = j; i < len; i++) {
				if (this.array[idx] > this.array[i]) {
					idx = i;
				}
			}
			tmp = this.array[j];
			this.array[j] = this.array[idx];
			this.array[idx] = tmp;
		}
	}

	public void mergeSort(int begin, int end) {
		if (end == begin)
			return;

		if (end == begin + 1) {
			if (this.array[begin] > this.array[end]) {
				int tmp = this.array[begin];
				this.array[begin] = this.array[end];
				this.array[end] = tmp;
			}
			return;
		}
		int middle = (end + 1 + begin) / 2;

		mergeSort(begin, middle - 1);
		mergeSort(middle, end);
		merge(begin, middle, end);

	}

	private void merge(int begin, int middle, int end) {
		List<Integer> tmpArray = new ArrayList();
		int i = begin, j = middle;
		if (begin < end) {
			for (; i <= middle - 1 && j <= end;) {
				if (this.array[i] > this.array[j]) {
					tmpArray.add(this.array[j]);
					j++;
				} else {
					tmpArray.add(this.array[i]);
					i++;
				}
			}
			for (; i <= middle - 1; i++) {
				tmpArray.add(this.array[i]);
			}
			for (; j <= end; j++) {
				tmpArray.add(this.array[j]);
			}
			for (i = 0; i < tmpArray.size(); i++) {
				this.array[begin + i] = tmpArray.get(i);
			}
		}
	}

	public static void main(String[] args) {
		Integer[] array = { 1, 6, 2, 3, 8, 5, 7, 4 };

		// Integer[] array = { 1,3,2 };

		Sort sort = new Sort(array);
		System.out.println("before : " + Arrays.toString(array));
		System.out.println("bubbleSort before : " + Arrays.toString(sort.getArray()));
		// sort.bubbleSort();
		// sort.insertionSort();
		// sort.quickSort(0, array.length - 1);
		// sort.selectionSort();
		sort.mergeSort(0, array.length - 1);
		System.out.println("after : " + Arrays.toString(array));
		System.out.println("bubbleSort after : " + Arrays.toString(sort.getArray()));

		
		ArrayList List = new ArrayList();
		for (int i = 0; i < 10; i++) // 给数组增加10个Int元素
			List.add(i);
		List.remove(5);// 将第6个元素移除
		System.out.println(List.toString());
		for (int i = 0; i < 3; i++) // 再增加3个元素
			List.add(i + 20);
		Object[] values = List.toArray();// 返回ArrayList包含的数组
		Integer[] values2 = (Integer[]) List.toArray(new Integer[List.size()]);
		System.out.println(values2[0]);
		
		// 创建ArrayList
        ArrayList list = new ArrayList();

        // 将“”
        list.add("1");
        list.add("2");
        list.add("3");
        list.add("4");
        // 将下面的元素添加到第1个位置
        list.add(0, "5");

        // 获取第1个元素
        System.out.println("the first element is: "+ list.get(0));
        // 删除“3”
        list.remove("3");
        // 获取ArrayList的大小
        System.out.println("Arraylist size=: "+ list.size());
        // 判断list中是否包含"3"
        System.out.println("ArrayList contains 3 is: "+ list.contains(3));
        // 设置第2个元素为10
        list.set(1, "10");

        // 通过Iterator遍历ArrayList
        for(Iterator iter = list.iterator(); iter.hasNext(); ) {
            System.out.println("next is: "+ iter.next());
        }

        // 将ArrayList转换为数组
        String[] arr = (String[])list.toArray(new String[0]);
        for (String str:arr)
            System.out.println("str: "+ str+","+arr.length);

        // 清空ArrayList
        list.clear();
        // 判断ArrayList是否为空
        System.out.println("ArrayList is empty: "+ list.isEmpty());
	}

	public Integer[] getArray() {
		return array;
	}

	public void setArray(Integer[] array) {
		this.array = array;
	}
}
